package lhc.alg.top100;

import java.util.Arrays;

/**
 * description: https://leetcode.cn/problems/valid-triangle-number/submissions/
 *  有效三角形个数  排序+二分查找
 * author: hongchen.liao
 * date:  2022/9/12
 */
public class _611_ {

    class Solution {
        public int triangleNumber(int[] nums) {
            int n = nums.length;
            Arrays.sort(nums);
            int ans= 0;
            for(int i = 0; i < n; i++){
                for(int j = i+1; j < n; j++){
                    int left = j+1, right =n-1, k = j;
                    while(left <= right){
                        int mid = (left + right)/2;
                        if(nums[mid] < nums[i] + nums[j]){
                            k = mid;
                            left = mid+1;
                        }else{
                            right = mid-1;
                        }
                    }
                    ans += k-j;
                }
            }
            return ans;
        }
    }

}
